package com.example.algorithm.hot_topic;

import com.example.algorithm.bean.TreeNode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Stack;

public class BinaryTree {
    //中序遍历
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        while(!stack.isEmpty() || root!=null) {
            //往左子树走，每走一次保存到栈
            //模拟递归调用
            if(root!=null) {
                stack.add(root);
                root = root.left;
            } else {
                //当前节点为空，左边到头，栈中弹出并保存
                //转向右边，继续
                TreeNode tmp = stack.pop();
                res.add(tmp.val);
                root = tmp.right;
            }
        }
        return res;
    }

    //    层序遍历
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if (root != null) queue.add(root);
        while (!queue.isEmpty()) {
            List<Integer> tmp = new ArrayList<>();
            for(int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                if (node!=null){
                    tmp.add(node.val);
                    if (node.left != null) queue.add(node.left);
                    if (node.right != null) queue.add(node.right);
                }
            }
            res.add(tmp);
        }
        return res;
    }

    //    前序，中序，恢复二叉树
    int[] preorder;
    HashMap<Integer, Integer> dic = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        //中序元素和索引映射
        for (int i = 0; i < inorder.length; i++)
            dic.put(inorder[i], i);
        return recur(0, 0, inorder.length - 1);
    }
    TreeNode recur(int root, int left, int right) {
        if (left > right)
            return null; // 递归终止
        TreeNode node = new TreeNode(preorder[root]); // 建立根节点
        int i = dic.get(preorder[root]); // 划分根节点、左子树、右子树
        node.left = recur(root + 1, left, i - 1); //左子树递归
        node.right = recur(root + i - left + 1, i + 1, right); //右子树递归
        return node; // 回溯返回根节点
    }

    //    最大深度
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }

    // 翻转二叉树
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        TreeNode tmp = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(tmp);
        return root;
    }

    //是否对称
    public boolean isSymmetric(TreeNode root) {
        return root == null || recur(root.left, root.right);
    }
    boolean recur(TreeNode L, TreeNode R) {
        if (L == null && R == null) return true;
        if (L == null || R == null || L.val != R.val) return false;
        return recur(L.left, R.right) && recur(L.right, R.left);
    }

    //二叉树直径：任意节点路径长度
    int ans = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return ans;
    }
    int dfs(TreeNode u) {
        if (u == null) return 0;
        int l = dfs(u.left), r = dfs(u.right);
        ans = Math.max(ans, l + r);
        return Math.max(l, r) + 1;
    }

    //二叉树右视图
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        dfs(root, 0, ans);
        return ans;
    }
    private void dfs(TreeNode root, int depth, List<Integer> ans) {
        if (root == null) {
            return;
        }
        if (depth == ans.size()) { // 这个深度首次遇到
            ans.add(root.val);
        }
        dfs(root.right, depth + 1, ans); // 先递归右子树，首次遇到的一定是最右边
        dfs(root.left, depth + 1, ans);
    }

    //二叉树转链表
    public void flatten(TreeNode root) {
        while (root != null) {
            // 左子树为 null，直接下一个
            if (root.left == null) {
                root = root.right;
            } else {
                //找左子树最右边节点
                TreeNode pre = root.left;
                while (pre.right != null) {
                    pre = pre.right;
                }
                // 将原右子树接到左子树最右边节点
                pre.right = root.right;
                // 将原左子树插入原右子树
                root.right = root.left;
                root.left = null;
                //下一个
                root = root.right;
            }
        }
    }

    //    和等于targetSum的路径数量
    private int ans1;
    public int pathSum(TreeNode root, int targetSum) {
        Map<Long, Integer> cnt = new HashMap<>();
        cnt.put(0L, 1);
        dfs(root, 0, targetSum, cnt);
        return ans1;
    }
    private void dfs(TreeNode node, long s, int targetSum, Map<Long, Integer> cnt) {
        if (node == null) {
            return;
        }
        s += node.val;
        ans1 += cnt.getOrDefault(s - targetSum, 0);
        cnt.merge(s, 1, Integer::sum);
        dfs(node.left, s, targetSum, cnt);
        dfs(node.right, s, targetSum, cnt);
        cnt.merge(s, -1, Integer::sum); // 恢复现场
    }

    //    最近公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left == null) return right;
        if(right == null) return left;
        return root;
    }

    //升序数组转搜索树
    public TreeNode sortedArrayToBST(int[] nums) {
        return dfs(nums, 0, nums.length - 1);
    }
    private TreeNode dfs(int[] nums, int lo, int hi) {
        if (lo > hi) {
            return null;
        }
        //中间元素为根
        int mid = lo + (hi - lo) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        // 递归构建
        root.left = dfs(nums, lo, mid - 1);
        root.right = dfs(nums, mid + 1, hi);
        return root;
    }

    //是否是搜索树
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    private boolean isValidBST(TreeNode node, long left, long right) {
        if (node == null) {
            return true;
        }
        long x = node.val;
        return left < x && x < right &&
                isValidBST(node.left, left, x) &&
                isValidBST(node.right, x, right);
    }

    //搜索树中第K小:中序遍历为升序
    int res, k;
    public int kthSmallest(TreeNode root, int k) {
        this.k = k;
        dfsSearch(root);
        return res;
    }
    void dfsSearch(TreeNode root) {
        if (root == null)
            return;
        dfsSearch(root.left);
        if (k == 0)
            return;
        if (--k == 0)
            res = root.val;
        dfsSearch(root.right);
    }
}
